The present invention relates to memory organization in computer systems. More specifically, the present invention relates to virtual memory systems having page tables that are accessed via a hash function.
Conventional computer systems use a technique called virtual memory that simulates more logical memory than actually exists and allows the computer to run several programs concurrently regardless of their size. Concurrent user programs access main memory addresses via virtual addresses assigned by the operating system. The mapping of the virtual addresses to the physical addresses of the main memory is a process known as virtual address translation. Virtual address translation can be accomplished by any number of techniques, thereby allowing the processor to access the desired information in main memory.
The virtual address and physical address spaces are typically divided into equal size blocks of memory called pages, and a page table provides the translation between virtual addresses and physical addresses. Each page table entry typically contains the virtual address and/or the physical address, and protection and status information concerning the page. Status typically includes information about the type of accesses the page has undergone. For example, a dirty bit indicates there has been a modification to data in the page. Because the page tables are usually large, they are stored in memory. Therefore each regular memory access can actually require at least two accesses, one to obtain the translation and a second to access the physical memory location.
Many computer systems that support virtual address translation use a translation lookaside buffer (TLB). The TLB is typically a small, fast, associative memory which is usually situated on or in close proximity to the processor unit and stores recently used pairs of virtual and physical addresses. The TLB contains a subset of the translations in the page table and can be accessed much more quickly. When the processing unit needs information from main memory, it sends the virtual address to the TLB. The TLB accepts the virtual address page number and returns a physical page number. The physical page number is combined with low order address information to access the desired byte or word in main memory.
In most cases, the TLB cannot contain the entire page table, so procedures need to be implemented to update the TLB. When a virtual page is accessed, the translation for which is not in the TLB, the page table is accessed to determine the translation of this virtual page number to a physical page number, and this information is entered in the TLB. Access to the page table can take twenty times longer than access to the TLB, and therefore program execution speed is optimized by keeping the translations being utilized in the TLB.
Most computer systems today use some sort of mass storage, typically a disk, to augment the physical random access (RAM) memory in the computer. This augmentation of main memory enables larger programs to be implemented than if only main memory were available. In addition, disk memory is considerably less expensive than RAM, but is also orders of magnitude slower. Depending on the length of a program and the competition with other programs for main memory, part of a program may reside in main memory and part may reside on disk at any particular point in time. The parts of a program that need to be accessed immediately are brought into main memory while the parts not currently used are left on the disk.
For example, consider a single program that is two megabytes long and is executed on a computer having one megabyte of main memory. The program will require two megabytes of virtual address space. Since the main memory can only hold one megabyte, at most half of the program can reside in main memory at any given time and the remainder of the virtual address space is stored on the disk. Access to the information in main memory occurs normally. That is, the TLB is looked to first to see if it has the translation, and if not in the TLB, the TLB is updated using information from the page table and then the TLB is again referenced to get the desired translation information.
If access to the information that is not in the main memory occurs, then the TLB is accessed first for the translation, which will not be there. Then the page table is referenced to get the translation information to update the TLB. However the page table only has the translations for information in main memory, and therefore will not have the required translation information. This condition is called a page fault. In response to a page fault, a page fault handler finds a free physical page, loads the physical page with the required virtual page stored on the disk, and inserts the translation into a page table. If all physical pages have already been associated with other virtual pages, then the page fault handler needs to select which virtual pages currently stored in physical memory to swap out to the disk. There are many algorithms for performing this task, such as the first-in-first-out and least-recently-used algorithms. The page fault handler is typically implemented in software, while the TLB update process can be handled either by hardware or software, as is well known in the art.
FIG. 1 illustrates the process described above. In step 112 a virtual address is 1 presented to the TLB. If the translation for that virtual address is in the TLB (a TLB hit), then the associated physical address is derived from the TLB and is utilized to access physical memory (step 114). If the translation for that virtual address is not in the TLB (a TLB miss), then the page table is accessed for the translation (step 116). If the translation is in the page table, then this information is inserted in the TLB (step 118) and the virtual address is again presented (step 112). This time there will be a TLB hit so that the resulting physical address is used to access physical memory.
If the virtual address is in a page of virtual addresses for which no page of physical addresses is associated, then there will be no entry for this page in the page table and a page fault will occur. In this situation, a software page fault handler (step 120) will assign a physical page to the virtual page, copy the page from disk to the physical page, and update the page table. Then the virtual address is again presented to the TLB. Since the TLB does not yet have the translation, there will be another TLB miss and the TLB will be updated from the page table. Thereafter, the virtual address is again presented to the TLB, and this time a TLB hit is assured and the resulting physical address is used to access physical memory.
FIG. 2 illustrates a simplified method of accessing an entry in a translation lookaside buffer (TLB) in response to the presentation of a virtual address. To simplify the example, the illustrated TLB has only one entry, whereas a TLB would normally have many more entries. The virtual address is loaded into a register 201. This virtual address is composed of two parts a virtual page number 203 and a physical offset 205. The physical offset corresponds to the page size. For a computer system having a page size of 4 kilobytes, the physical offset 205 is the lower 12 bits (bits 11-0) of the address and specifies a particular byte within a page. The remaining bits in the register indicate the virtual page number. The term xe2x80x9cpage offsetxe2x80x9d is a term often used in the industry and is synonymous with the term xe2x80x9cphysical offsetxe2x80x9d. The virtual address may include other bits that are used in uniquely specifying a translation to a physical page number, such as xe2x80x9caddress space identifierxe2x80x9d bits or xe2x80x9cregion identifierxe2x80x9d bits.
For the example illustrated, the virtual page number becomes the virtual tag, which supplies one input for the TLB comparator 207. A TLB 209 has two linked parts, a TLB tag 211 and an associated physical page number 213. The TLB tag 211 supplies the second input to the TLB comparator 207 and the comparator compares the TLB tag to the virtual tag. If the tags match, then the comparator indicates a TLB hit and the physical page number 213 is combined with the physical offset 205 to provide the physical (real) memory address. If the tags do not match, then there has been a TLB miss and the TLB miss process described in association with FIG. 1 is employed to update the TLB.
FIG. 3 illustrates the process of retrieving the physical page information given the virtual page number as would be required to update the TLB after a TLB miss. As described above, the virtual-to-physical mappings are maintained in a page table. For translating a given virtual address to a physical address, one approach is to perform a many-to-one (hash) function on the virtual address to form an index into the page table. This gives a pointer to a linked list of entries. These entries are then searched for a match. To determine a match, the virtual page number is compared to an entry in the page table (virtual tag). If the two are equal, that page table entry provides the physical address translation.
In the example illustrated, a hash function 301 is performed on the virtual page number 203 to form an index. This index is an offset into the page table 303. As shown, the index is 0, that is, the index points to the first entry 305 in the page table. Each entry in the page table consists of multiple parts, but typically includes at least a virtual tag 307, a physical page 309 and a pointer 311. If the virtual page number 203 equals the virtual tag 307, then physical page 309 gives the physical (real) memory page address desired. If the virtual tag does not match, then the pointer 311 points to a chain of entries in memory which contain virtual to physical translation information. The additional information contained in the chain is needed as more than one virtual page number can hash to the same page table entry.
As shown, pointer 311 points to a chain segment 313. This chain segment contains the same type of information as the initial page table entries. As before, the virtual page number 203 is compared to the next virtual tag 315 to see if there is a match. If a match occurs, then the associated physical page 317 gives the address ofthe physical memory page desired. If a match does not occur, then the pointer 319 is examined to locate the next chain segment, if any. If the pointer 319 does not point to another chain segment, as shown, then a page fault has occurred. A page fault software program is then used, as described in association with FIG. 1, to update the page table.
The above described method works well for systems where the virtual TAG is less than or equal to the basic data path size of the computer. However, if the virtual TAG is larger than the data path size, then two compares are required to test if the virtual TAG and the virtual page number are the same.
U.S. Pat. No. 5,724,538 to Dale Morris et al, which is entitled xe2x80x9cComputer Memory Address Control Apparatus Utilizing Hashed Address Tags in Page Tables Which Are Compared to a Combined Address Tag and Index Which Are Longer than the Basic Data Width of the Associated Computerxe2x80x9d and is hereby incorporated by reference, discloses a scheme for reducing the size of the virtual tag, thereby reducing the number of compares required to test if the virtual TAG and the virtual page number are the same. Basically, Morris et al recognized that part of the virtual address is already represented by the hash index, and therefore that part of the address need not be represented by the virtual tag.
FIG. 4 shows a simplified block diagram of an embodiment disclosed by Dale Morris et al. In FIG. 4, the page table 413 contains xe2x80x9chash tagsxe2x80x9d 421 and 423. Hash index 409 is formed by taking the virtual page number bits 401 and performing an index hash function 405 on the bits, with the result being no larger than the basic data width of the computer. Similarly, the hash tags are formed by taking the virtual page number bits 401 and performing a tag hash function 427, with the resulting hash tags being no larger than the basic data width of the computer. Note that although FIG. 4 does not show an explicit connection between tag hash function 427 and hash tags 421 and 423, the algorithm represented by tag hash function 427 is used when hash tags 421 and 423 are generated and inserted into page table 413.
Index hash function 405 and tag hash function 427 are complimentary to the extent that for any given virtual page number, the combination of the resulting hash index and the resulting hash tag are unique. Accordingly, when a virtual page is to be accessed, the virtual page number 401 is applied to index hash function 405 to generate a hash index, which points to a hash tag (such as hash tag 421 or 423) in page table 413. The hash tag provided from table 413 is routed to compare function 429. Simultaneously, virtual page number 401 is also provided to tag hash function 427 to produce hash tag 425. If hash tag 425 and the hash tag from page table 413 match, then the physical page (such as the physical pages stored at entries 317 and 417) is used to complete the memory access operation. If the tags do not match, the pointer of the page table entry (such as pointers 319 and 419) are accessed to see if a chain segment exists. If there are no chain segments, or all chain segments have been searched without finding a match, then the page fault handler of the operating system is invoked, as described above.
Note that the index hash function 405 and the tag hash function 427 are accessed by both hardware and software. Hardware must access the hash functions when translating a virtual page number to a physical page number, and software must access the hash functions when initializing the page table, and when accessing and modifying the page table, such as required when servicing a page fault. In the prior art, the hash algorithms were, in essence, provided in two forms. Computer hardware included hardware-based versions of the hash algorithms to allow virtual-to-physical translations to proceed quickly, and the operating system included software-based versions of the hash algorithms to generate virtual-to-physical translations when initializing, accessing, or modifying the page table.
Some computers expand the virtual addressing concept by supporting regions. Regions provide the capability to effectively create independent local, shared and global address spaces within the virtual address space by dividing the virtual address space into equally sized regions. Typically, only a subset of regions can be active at any time. Associated with each region is a region identifier, which uniquely tags address translations of given regions. If the region identifier for a region is assigned to a particular process, this region space becomes local to that process. If the region identifier for a region is shared among processes, this region space becomes shared. If the region identifier for a region is shared by all processes, this region becomes global. Changing the region identifiers for the local regions effectively swaps virtual addresses from the local space of one process to the local space on another process. Thus, regions virtually eliminate the need to flush the TLB when switching process, thereby improving overall system performance.
The present invention is a method and apparatus for calculating a page table index from a virtual address. The present invention is implemented by a combined hash algorithm that supports two different hash page table configurations in a single computer architecture via configuration registers and predefined constants.
The present invention can be used, for example, in conjunction with a virtual addressing scheme having a 64-bit virtual address, with the upper three bits forming a virtual region portion. Accordingly, eight regions can be specified by a virtual address at any given time. The remaining 61 bits of the virtual address are used to address memory within each region, thereby providing each region with 261 bytes of virtual memory. Associated with each memory page is a 24-bit region identifier. Therefore, the operating system can assign up to 224 individual virtual address spaces. Memory pages can range in size from 4 kilobytes to 256 megabytes.
The first hash page table configuration supports a region-based linear page table, and will be referred to herein as a xe2x80x9cshort formatxe2x80x9d page table. A short format page table is provided for each virtual region, is linear, and has a linear entry for each translation in the region. The short format page table does not require chain segments, and the short format page table does not include hash tag entries. The second hash page table configuration supports a single page table for the entire computer system and will be referred to herein as a xe2x80x9clong formatxe2x80x9d page table. The long format page table supports chain segments, and long format page table entries include a hash tag field.
In one embodiment, the method of the present invention forms an entry address from a virtual address, with the entry address referencing an entry of the page table. To form the entry address, first a hash page number is formed from the virtual address by shifting the virtual address right by J bits, wherein the preferred page size of the region associated with the region portion of the virtual address is 2J bytes.
If the computer system is operating with long format page tables, the next step is to form a hash index by combining the hash page number and the region identifier referenced by the region portion of the virtual address, and to form a table offset by shifting the hash index left by K bits, wherein each long format page table entry is 2K bytes long.
However, if the computer system is operating with short format page tables, the next step is to form a hash index by setting the hash index equal to the hash page number, and to form a table offset by shifting the hash index left by L bits, wherein each short format page table entry is 2L bytes long.
Next, a mask is formed based on the size of the page table. A first address portion is then formed using the base address of the page table and the mask, and a second address portion is formed using the table offset and the mask. Finally, the entry address is formed by combining the first and second address portions.
In another embodiment, a region portion is inserted into the entry address. If the format is set to long, the region portion is derived from the region portion of the base address of the page table. However, if the region is set to short, the region portion is derived from the region portion of the virtual address.
In yet another embodiment, the maximum size of a long format page table is increased by inserting the region portion of the virtual address into the hash page number when the format is set to long.
The present invention also includes several embodiments that reduce the amount of logic used to implement the present invention based on certain implementation dependant parameters. By providing a single algorithm capable of generating a page table entry for both long and short format page tables, the present invention reduces the amount of logic required to access both page table formats, without significantly affecting execution speed.